package com.zsj.basicMathComputed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;

/**
 * @auther zsj
 * @Date 2021/12/9
 * 二分法查找
 * 二分法查找要求数组必须是一个有序数组
 * 寻找数组中的数据
 * 找到返回下标
 * 没找到返回-1
 **/
public class DichotomySearch {

    public static void main(String[] args) {

        char [] s = {'h','e','l','l','o'};
        reverseString(s);
        for (char c : s) {
            System.out.print(c+" ");
        }
    }

    /**
     * 二分法查找
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        Arrays.sort(nums);
        int begin = 0;
        int end = nums.length - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;

    }


    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
     * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 请必须使用时间复杂度为 O(log n) 的算法。
     * <p>
     * <p>
     * 思路
     * 数的范围是在是在0-nums的长度里的,我们只需要返回对应数组下标即可
     * 也就是判断nums[length]=target ,返回这个length
     * <p>
     * 当数组中没有这个数据
     * 判断
     */
    public static int searchInsert(int[] nums, int target) {
        //这一道题就是在二分查找的基础上加了一点点？
        int left = 0;
        int right = nums.length - 1;
        if (target < nums[left]) {
            //说明目标值比所有的值都要小
            return left;
        } else if (target > nums[right]) {
            //说明目标值比所有的值都要大
            return nums.length;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;//防止整型溢出
            if (nums[mid] == target) {
                //如果数据正好在最中间，直接返回下标
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;//小于说明,数据在右边mid--right的区间
            } else if (nums[mid] > target) {
                right = mid - 1;//小于说明,数据在左边left--mid的区间
            }
        }
        return left;
    }

    /**
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * <p>
     * <p>
     * 输入：nums = [-4,-1,0,3,10]
     * 输出：[0,1,9,16,100]
     * 解释：平方后，数组变为 [16,1,0,9,100]
     * 排序后，数组变为 [0,1,9,16,100]
     * <p>
     * <p>
     * 思路
     * 不管是什么数字，他的平方就一定为正数,那这个数组的顺序就一定是一个有序数组
     * 遍历数组中的数据并一个一个添加到新数组中去，然后排序即可
     *
     * @return
     */
    public static int[] sortedSquares(int[] nums) {
        int[] clone = nums.clone();
        Arrays.sort(clone);
        for (int i = 0; i < clone.length; i++) {
            clone[i] = clone[i] * clone[i];
        }
        Arrays.sort(clone);
        return clone;
    }


    /**
     * 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     * <p>
     * 输入: nums = [1,2,3,4,5,6,7], k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右轮转 1 步: [7,1,2,3,4,5,6]
     * 向右轮转 2 步: [6,7,1,2,3,4,5]
     * 向右轮转 3 步: [5,6,7,1,2,3,4]
     * 我们可以使用额外的数组来将每个元素放至正确的位置。
     * 用 nn 表示数组的长度，我们遍历原数组，将原数组下标为 ii 的元素放至新数组下标为 (i+k)\bmod n(i+k)modn 的位置，
     * 最后将新数组拷贝至原数组即可。
     */
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }


    /**
     * 给定一个整数数组 nums和一个整数目标值 target，
     * 请你在该数组中找出 和为目标值 target的那两个数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案。
     */
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; ++i) {//执行三次 0-1 0-2 1-
            for (int j = i + 1; j < nums.length; ++j) {//执行两次
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     */
    public static void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
        for (int num : nums) {
            System.out.println(num);
        }
    }


    /**
     * 给定一个已按照 非递减顺序排列 的整数数组numbers ，
     * 请你从数组中找出两个数满足相加之和等于目标数target 。
     * <p>
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。
     * numbers的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
     * <p>
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素
     */
    public static int[] twoSumIndex(int[] numbers, int target) {
        int[] result = new int[2];//初始化结果数组
        int len = numbers.length;
        //遍历数组
        for (int i = 0; i < len; i++) {
            //在遍历一次拿到往后移一位的数字
            for (int j = i + 1; j < len; j++) {
                if (numbers[i] + numbers[j] == target) {
                    //为目标值
                    result[0] = i + 1;
                    result[1] = j + 1;
                }
            }
        }
        return result;
    }

    /**
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * <p>
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题
     * @param s
     */
    public static void reverseString(char[] s) {
        //使用双指针算法,指定数组的开头和结尾的数组，每次循环交换位置并将开头++和结尾--
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char temp = s[right];
            s[right] =s[left];
            s[left] = temp;
        }
    }

    //接受字符串返回的方法
    public String getString(){

        return  null;
    }


}





